// https://leetcode.cn/problems/champagne-tower/
#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    // 逐层往下倒
    double champagneTower1(int poured, int query_row, int query_glass)
    {
        vector<vector<double>> dp(101, vector<double>(101, 0.0));
        dp[0][0] = (double)poured;
        int flag = 0;
        for (int i = 0; i <= query_row; i++)
        {
            for (int j = 0; j <= i; j++)
            {
                if (dp[i][j] > 1)
                {
                    dp[i + 1][j] += (dp[i][j] - 1) / 2;
                    dp[i + 1][j + 1] += (dp[i][j] - 1) / 2;
                    dp[i][j] = 1;
                }
            }
        }
        return dp[query_row][query_glass];
    }

    double champagneTower(int poured, int query_row, int query_glass)
    {
        vector<double> dp = {double(poured)};
        for (int i = 1; i <= query_row; i++)
        {
            vector<double> tmp(i + 1, 0);
            for (int j = 0; j < i; j++)
            {
                if (dp[j] > 1)
                {
                    tmp[j] += (dp[j] - 1) / 2;
                    tmp[j + 1] += (dp[j] - 1) / 2;
                }
            }
            dp = tmp;
        }
        return min(1.0, dp[query_glass]);
    }
};

int main()
{
    Solution so;
    cout << so.champagneTower(2, 1, 1) << endl;
    return 0;
}